//编写一个程序，反转链表并返回反转后的链表
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct ListNode {
    int val;// 节点值
    struct ListNode *next;// 指向下一个节点的指针
};

// 创建新节点
struct ListNode* createNode(int val) {// 创建新节点
    // 分配内存并初始化节点
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;// 设置节点值
    newNode->next = NULL;// 初始化下一个节点指针为NULL
    return newNode;// 返回新创建的节点
}

// 迭代法反转链表
struct ListNode* reverseListIterative(struct ListNode* head) {
    struct ListNode* prev = NULL;    // 前一个节点
    struct ListNode* curr = head;    // 当前节点
    
    while (curr != NULL) {
        struct ListNode* nextTemp = curr->next;  // 保存下一个节点
        curr->next = prev;           // 反转指针方向
        prev = curr;                 // 前移prev指针
        curr = nextTemp;             // 前移curr指针
    }
    
    return prev;  // 返回新的头节点
}

// 递归法反转链表
struct ListNode* reverseListRecursive(struct ListNode* head) {
    // 递归终止条件：空链表或只有一个节点
    if (head == NULL || head->next == NULL) {
        return head;// 返回头节点
    }
    
    // 递归反转剩余部分
    struct ListNode* newHead = reverseListRecursive(head->next);
    
    // 将当前节点的下一个节点的next指向当前节点
    head->next->next = head;
    // 断开当前节点的next指针
    head->next = NULL;
    
    return newHead;// 返回新的头节点
}

// 打印链表
void printList(struct ListNode* head) {
    struct ListNode* current = head;// 从头节点开始遍历
    while (current != NULL) {// 遍历链表
        printf("%d", current->val);// 打印当前节点值
        if (current->next != NULL) {// 如果不是最后一个节点，打印箭头
            printf(" -> ");
        }
        current = current->next;// 移动到下一个节点
    }
    printf("\n");
}

// 释放链表内存
void freeList(struct ListNode* head) {
    struct ListNode* current = head;// 从头节点开始遍历
    while (current != NULL) {// 遍历链表
        struct ListNode* temp = current;// 临时保存当前节点
        current = current->next;// 移动到下一个节点
        free(temp);// 释放当前节点内存
    }
}

// 测试函数
int main() {
    // 创建测试链表: 1 -> 2 -> 3 -> 4 -> 5
    struct ListNode* head = createNode(1);// 创建头节点
    head->next = createNode(2);// 创建第二个节点
    head->next->next = createNode(3);// 创建第三个节点
    head->next->next->next = createNode(4);// 创建第四个节点
    head->next->next->next->next = createNode(5);// 创建第五个节点
    
    printf("原始链表: ");
    printList(head);// 打印原始链表
    
    // 使用迭代法反转链表
    struct ListNode* reversedIterative = reverseListIterative(head);
    printf("迭代法反转后: ");
    printList(reversedIterative);// 打印反转后的链表
    
    // 使用递归法反转链表
    struct ListNode* reversedRecursive = reverseListRecursive(reversedIterative);
    printf("递归法反转后: ");
    printList(reversedRecursive);// 打印反转后的链表
    
    // 测试边界情况
    printf("\n边界情况测试:\n");
    
    // 空链表
    struct ListNode* emptyList = NULL;
    struct ListNode* reversedEmpty = reverseListIterative(emptyList);// 反转空链表
    printf("空链表反转后: ");
    printList(reversedEmpty);// 打印反转后的链表
    
    // 只有一个节点的链表
    struct ListNode* singleNode = createNode(42);// 创建单节点链表
    printf("单节点链表: ");
    printList(singleNode);// 打印单节点链表
    // 反转单节点链表
    struct ListNode* reversedSingle = reverseListIterative(singleNode);
    printf("单节点链表反转后: ");
    printList(reversedSingle);// 打印反转后的链表
    
    // 释放内存
    freeList(reversedRecursive);
    freeList(reversedEmpty);
    freeList(reversedSingle);
    
    return 0;// 程序结束
}